package code.oldCode.feishuSpecializedTraining.greedy;

import java.util.Arrays;

/**
 * @author 26029
 * @date 2025/3/19
 * @description
 */
public class MyGreedy {
    // 455. 分发饼干
    public int findContentChildren(int[] g, int[] s) {
        int gLen = g.length, sLen = s.length;
        Arrays.sort(g);
        Arrays.sort(s);
        int gPos = 0, sPos = 0;
        while (gPos < gLen && sPos < sLen) {
            if (g[gPos] <= s[sPos]) {
                gPos++;
            }
            sPos++;
        }
        return gPos;
    }

    // 376. 摆动序列
    public int wiggleMaxLength(int[] nums) {
        // 直观的方法：只需要统计方向变更的次数即可，结果为变更次数+1，本质上也是贪心
        // [1,17,5,10,13,15,10,5,16,8]
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return 1;
        int direction = 0;
        int changes = 0;
        for (int i = 1; i < nums.length; i++) {
            // 方向变更：当前值与上一个值的差比较，方向与之前的方向不同，且这俩值不相等的情况
            if (Integer.compare(nums[i], nums[i - 1]) != direction && nums[i] != nums[i - 1]) {
                direction = Integer.compare(nums[i], nums[i - 1]);
                changes++;
            }
        }
        return changes + 1;
    }

    public int wiggleMaxLength_greedy(int[] nums) {
        // 贪心的方法：官解，找峰和谷，类似
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return 1;
        int direction = nums[1] - nums[0];
        int count = direction == 0 ? 1 : 2;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 0 && direction <= 0 || nums[i] - nums[i - 1] < 0 && direction >= 0) {
                direction = nums[i] - nums[i - 1];
                count++;
            }
        }
        return count;
    }

    public int wiggleMaxLength_dp(int[] nums) {
        // 动态规划的做法：有点类似股票问题
        // 某个序列被称为「上升摆动序列」，当且仅当该序列是摆动序列，且最后一个元素呈上升趋势。如序列 [1,3,2,4] 即为「上升摆动序列」。
        // 某个序列被称为「下降摆动序列」，当且仅当该序列是摆动序列，且最后一个元素呈下降趋势。如序列 [4,2,3,1] 即为「下降摆动序列」。
        if (nums == null || nums.length == 0)
            return 0;
        if (nums.length == 1)
            return 1;
        // up[i] = (nums[i] > nums[i-1]) ? max(up[i-1], down[i-1] + 1) : up[i-1]
        int[] up = new int[nums.length]; // up[i] 为前i个元素以某个为结尾的上升摆动序列的最大长度
        int[] down = new int[nums.length]; // up[i] 为前i个元素以某个为结尾的下降摆动序列的最大长度
        up[0] = down[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            up[i] = (nums[i] > nums[i-1]) ? Math.max(up[i-1], down[i-1] + 1) : up[i-1];
            down[i] = (nums[i] < nums[i - 1]) ? Math.max(down[i - 1], up[i - 1] + 1) : down[i - 1];
        }
        return Math.max(up[nums.length - 1], down[nums.length - 1]);
    }

    // 53. 最大子数组和
    public int maxSubArray(int[] nums) {
        // 贪心，当前sum大于0，则一直加
        int nowSum = 0, maxSum = Integer.MIN_VALUE;
        for (int num : nums) {
            if (nowSum < 0)
                nowSum = 0;
            nowSum += num;
            maxSum = Math.max(maxSum, nowSum);
        }
        return maxSum;
    }

    public int maxSubArray_dp(int[] nums) {
        // 动态规划
        int len = nums.length;
        int[] dp = new int[len]; // dp[i] 表示前i个中截至为i的连续子数组最大和
        dp[0] = nums[0];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < len; i++) {
            // 要么接着上一个，要么自己新开始，看哪个大
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
